#include<iostream>
#include<stdio.h>
using namespace std;
int n;
int main()
{
	int arr[1010] = { 0 };
	while (~scanf("%d",&n),n) {
		arr[2] = 2;
		arr[3] = 2;
		for (int i = 4; i < 1005; i++) {
			if (i % 2 == 0) {
				arr[i] = arr[i - 1] * 2 + 2;
				arr[i] %= 10000;
			}
			else {
				arr[i] = arr[i - 1] * 2 - 2;
				arr[i] %= 10000;
			}	
		}
		cout << arr[n] % 10000<< endl;
	}
	return 0;
}